﻿namespace Leetcode.N0029;

public class Solution
{
    public int Divide(int dividend, int divisor)
    {
        bool flg = true;
        long dividend2 = dividend;
        long divisor2 = divisor;

        if (dividend < 0)
        {
            dividend2 = -((long)dividend);
            flg = divisor < 0;
        }

        if (divisor < 0)
        {
            divisor2 = -((long)divisor);
            flg = dividend < 0;
        }

        var list = new List<long>();
        list.Add(divisor2);
        while (dividend2 - list[list.Count - 1] >= list[list.Count - 1])
        {
            list.Add(list[list.Count - 1] + list[list.Count - 1]);
        }

        long ans = 0;

        for (int i = list.Count - 1; i >= 0 && dividend2 >= divisor; i--)
        {
            if (dividend2 < list[i])
            {
                continue;
            }

            ans += (long)1 << i;
            dividend2 -= list[i];
        }
        ans = flg ? ans : -ans;
        return (ans > int.MaxValue) ? int.MaxValue : (int)ans;
    }
}